#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <fstream>
#include <string>
#include <chrono> // 包含时间库
#include <pthread.h>
#include <set>
#include <cmath>
#include <queue>
#include "node.h"

using namespace std;
// 线程锁
pthread_mutex_t g_mutex;
string input_path[] = {"input.txt"};
string output_path = "output.txt";
int n;                    // 卡的数量
int m;                    // 算子的数量
int id;                   // 算子id
int pre_cnt;              // 前驱算子数量
long long cal_use_time;   // 计算耗时
long long trans_use_time; // 传输耗时
vector<int> ids;
// unordered_map<int, int> id_to_index;
int pre_id;
vector<vector<int>> pre_ids;
vector<long long> cal_use_times;
vector<long long> trans_use_times;
vector<Node *> nodes;

// 处理输入
void init(const std::string &input_file)
{
    ifstream fin(input_file);
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> id;
        ids.push_back(id);
        fin >> pre_cnt;
        pre_ids.push_back(vector<int>());
        vector<Node *> in;
        for (int j = 0; j < pre_cnt; j++)
        {
            fin >> pre_id;
            in.emplace_back(nodes[pre_id]);
            pre_ids[i].push_back(pre_id);
        }
        fin >> cal_use_time;
        cal_use_times.push_back(cal_use_time);
        fin >> trans_use_time;
        trans_use_times.push_back(trans_use_time);
        nodes.emplace_back(new Node(id, in, cal_use_time, trans_use_time));
    }
}
void show()
{
    cout << "n:" << n << endl;
    cout << "m:" << m << endl;
    for (int i = 0; i < m; i++)
    {
        cout << "id:" << ids[i] << endl;
        cout << "pre_ids:";
        for (int j = 0; j < pre_ids[i].size(); j++)
        {
            cout << pre_ids[i][j] << " ";
        }
        cout << endl;
        cout << "cal_use_time:" << cal_use_times[i] << endl;
        cout << "trans_use_time:" << trans_use_times[i] << endl;
    }
}
long long cal_std(long long sum, long long sum2, int count)
{
    if (count == 0)
        return 0;
    long long mean = sum / count;
    long long variance = (sum2 / count) - mean * mean;
    if (variance < 0)
        variance = 0;
    return (long long)sqrt(variance);
}
class Solution
{
private:
    int n;
    int m;
    int *op_result_card; // 算子结果所在卡
    long long *last_trans_end_t; // 上次传输结束时间
    int *sz;
    long long *prio;  // 算子优先级
    long long *prio2; // 算子优先级2
    long long *cal_cost_sum;
    long long *cal_cost2_sum; // cal_cost平方的和
    int *heads;
    int *nex;
    int *to;
    int ecnt;
    int *rheads;
    int *rnex;
    int *rto;
    int recnt;
    long long *cal_cost;
    long long *trans_cost;
    int *in_degree;
    int *out_degree;
    int st;
    int en;
    int *unordered_q;
    set<pair<long long, int>> q;  // 基于优先级排序的算子队列
    set<pair<long long, int>> q2; // 基于优先级排序的算子队列2
    long long *q_free_t;
    vector<pair<int, int>> res; // 卡id,算子id
    vector<pair<int, int>> best_res;
    long long cost;
    long long best_cost;
    bool *accessed;
    int cnt_from_last_optimize;
public:
    Solution(int n, int m, const vector<vector<int>> &pre_ids, vector<long long> &cal_use_times, vector<long long> &trans_use_times)
    {
        best_cost = -1;
        this->n = n;
        this->m = m;
        op_result_card = new int[m];
        last_trans_end_t = new long long[m];
        sz = new int[m];
        prio = new long long[m];
        prio2 = new long long[m];
        cal_cost_sum = new long long[m];
        cal_cost2_sum = new long long[m];
        heads = new int[m];
        rheads = new int[m];
        int sum = 0;
        for (int i = 0; i < pre_ids.size(); i++)
        {
            sum += pre_ids[i].size();
        }
        nex = new int[sum];
        rnex = new int[sum];
        to = new int[sum];
        rto = new int[sum];
        cal_cost = new long long[m];
        trans_cost = new long long[m];
        in_degree = new int[m];
        out_degree = new int[m];
        unordered_q = new int[m];
        q_free_t = new long long[n];
        accessed = new bool[m];
        for (int i = 0; i < m; i++)
        {
            heads[i] = -1;
            rheads[i] = -1;
            cal_cost[i] = cal_use_times[i];
            trans_cost[i] = trans_use_times[i];
            prio[i] = 0;
            sz[i] = 1;
            cal_cost_sum[i] = cal_cost[i];
            cal_cost2_sum[i] = cal_cost[i] * cal_cost[i];
        }
        recnt = 0;
        ecnt = 0;
        for (int i = 0; i < pre_ids.size(); i++)
        {
            for (int j = 0; j < pre_ids[i].size(); j++)
            {
                nex[ecnt] = heads[pre_ids[i][j]];
                rnex[recnt] = rheads[i];
                to[ecnt] = i;
                rto[recnt] = pre_ids[i][j];
                heads[pre_ids[i][j]] = ecnt++;
                rheads[i] = recnt++;
                out_degree[pre_ids[i][j]]++;
            }
        }
        st = 0;
        en = 0;
        // 计算优先级
        for (int i = 0; i < m; i++)
            if (out_degree[i] == 0)
            {
                unordered_q[en++] = i;
            }
        while (st < en)
        {
            int op = unordered_q[st++];
            prio2[op] = cal_cost_sum[op] / sz[op] + cal_std(cal_cost_sum[op], cal_cost2_sum[op], sz[op]);
            for (int i = rheads[op]; i != -1; i = rnex[i])
            {
                int pre_op = rto[i];
                prio[pre_op] = max(prio[op] + cal_cost[op], prio[pre_op]);
                // prio[pre_op] = max(prio[pre_op] + cal_cost[op], prio[op]);
                sz[pre_op] += sz[op];
                cal_cost_sum[pre_op] += cal_cost_sum[op];
                cal_cost2_sum[pre_op] += cal_cost2_sum[op];
                out_degree[pre_op]--;
                if (out_degree[pre_op] == 0)
                {
                    unordered_q[en++] = pre_op;
                }
            }
        }
        cnt_from_last_optimize = 0;
    }
    int get_rand_operator()
    {
        swap(unordered_q[st], unordered_q[st + rand() % (en - st)]);
        q.erase({-prio[unordered_q[st]], unordered_q[st]});
        return unordered_q[st++];
    }
    int get_prio_operator()
    {
        auto it = q.begin();
        int op = it->second;
        q.erase(it);
        q2.erase({-prio2[op], op});
        return op;
    }
    int get_prio_2_operator()
    {
        auto it = q2.begin();
        int op = it->second;
        q.erase({-prio[op], op});
        q2.erase(it);
        return op;
    }
    int get_nex_operator()
    {
        if (rand() % 3 == 0 )
            return get_rand_operator();
        else
            return get_prio_operator();
    }
    int get_random_card()
    {
        return rand() % n;
    }
    int get_cal_t_min_card(int op)
    {
        int card = -1;
        long long cal_end_min = -1;
        vector<int> v;
        for (int i = rheads[op]; i != -1; i = rnex[i])
        {
            int pre_op = rto[i];
            v.emplace_back(pre_op);
        }
        sort(v.begin(), v.end(), [&](int i, int j) {
            return last_trans_end_t[i] < last_trans_end_t[j];
        });
        for (int i = 0; i < n; i++)
        {
            long long tmp = q_free_t[i];
            for (auto pre_op : v)
            {
                if (last_trans_end_t[pre_op] > tmp) {
                    tmp = last_trans_end_t[pre_op];
                }
                int result_card = op_result_card[pre_op];
                tmp += ((result_card == card) ? 0 : trans_cost[pre_op]);
            }
            tmp += cal_cost[op];
            if (cal_end_min == -1 || tmp < cal_end_min)
            {
                cal_end_min = tmp;
                card = i;
            }
        }
        return card;
    }
    int get_q_free_t_min_card()
    {
        int card = -1;
        long long q_free_t_min = -1;
        for (int i = 0; i < n; i++)
        {
            if (q_free_t_min == -1 || q_free_t[i] < q_free_t_min)
            {
                q_free_t_min = q_free_t[i];
                card = i;
            }
        }
        return card;
    }
    int get_user_free_card(int op)
    {
        return get_cal_t_min_card(op);
        // return rand() % n;
    }
    void work()
    {
        for (int i = 0; i < n; i++)
        {
            q_free_t[i] = 0;
        }
        for (int i = 0; i < m; i++)
        {
            in_degree[i] = 0;
            accessed[i] = false;
            last_trans_end_t[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            for (int j = heads[i]; j != -1; j = nex[j]) {
                in_degree[to[j]]++;
            }
        }
        st = 0;
        en = 0;
        q.clear();
        q2.clear();
        for (int i = 0; i < m; i++)
            if (in_degree[i] == 0)
            {
                unordered_q[en++] = i;
                q.insert({-prio[i], i});
                q2.insert({-prio2[i], i});
            }
        cost = 0;
        res.clear();
        while (!q.empty())
        {
            int op = get_nex_operator();
            
            if (accessed[op])
                continue;
            accessed[op] = true;
            int card = get_user_free_card(op);
            long long start_t = q_free_t[card];
            vector<int> v;
            for (int i = rheads[op]; i != -1; i = rnex[i])
            {
                int pre_op = rto[i];
                v.emplace_back(pre_op);
            }
            sort(v.begin(), v.end(), [&](int i, int j) {
                return last_trans_end_t[i] < last_trans_end_t[j];
            });
            for (auto pre_op : v) {
                if (last_trans_end_t[pre_op] > start_t) {
                    start_t = last_trans_end_t[pre_op];
                }
                int result_card = op_result_card[pre_op];
                start_t += ((result_card == card) ? 0 : trans_cost[pre_op]);
            }
            op_result_card[op] = card;
            last_trans_end_t[op] = start_t + cal_cost[op];
            cost = max(cost, last_trans_end_t[op]);
            q_free_t[card] = last_trans_end_t[op];
            for (int i = rheads[op]; i != -1; i = rnex[i])
            {
               
                int pre_op = rto[i];
                last_trans_end_t[pre_op] = start_t;
                op_result_card[pre_op] = card;
            }
            res.push_back({op, card});
            for (int i = heads[op]; i != -1; i = nex[i])
            {
                int nex_op = to[i];
                in_degree[nex_op]--;
                if (in_degree[nex_op] == 0)
                {
                    unordered_q[en++] = nex_op;
                    q.insert({-prio[nex_op], nex_op});
                    q2.insert({-prio2[nex_op], nex_op});
                }
            }
        }
        if (best_cost == -1 || cost < best_cost)
        {
            cnt_from_last_optimize = 0;
            best_cost = cost;
            best_res = res;
            cout << "find best cost:" << best_cost << endl;
        }
        else
        cnt_from_last_optimize++;
    }
  
    void write_res_to_file(string output_path)
    {
        pthread_mutex_lock(&g_mutex);
        // 追加写
        sort(res.begin(), res.end(), [](pair<int, int> &a, pair<int, int> &b)
             { return a.second < b.second; });
        ofstream fout(output_path, ios::app);
        fout << cost << endl;
        fout << '[';
        for (int i = 0; i < res.size(); i++)
        {
            fout << res[i].first;
            if (i != res.size() - 1)
                fout << ',';
        }
        fout << ']' << endl;
        pthread_mutex_unlock(&g_mutex);
    }
    void show_best_res(vector<int> &ids)
    {
        for (int i = 0; i < best_res.size(); i++)
        {
            cout << "op_id:" << best_res[i].first << " card_id:" << ids[best_res[i].second] << endl;
        }
        cout << "best_cost:" << best_cost << endl;
    }
    pair<long long, vector<pair<int, int>>> get_best_res()
    {
        return {best_cost, best_res};
    }
    static void merge_best_res(Solution &sol1, Solution &sol2)
    {
        if (sol1.best_cost == -1)
        {
            sol1.best_cost = sol2.best_cost;
            sol1.best_res = sol2.best_res;
        }
        else if (sol2.best_cost != -1 && sol2.best_cost < sol1.best_cost)
        {
            sol1.best_cost = sol2.best_cost;
            sol1.best_res = sol2.best_res;
        }
    }
    void cp_best_res(Solution &sol)
    {
        best_cost = sol.best_cost;
        best_res = sol.best_res;
    }
    void optimize_best_res()
    {
        // TODO 局部优化
        res = best_res;
        cost = 0;
        for (int i = 0; i < n; i++)
        {
            q_free_t[i] = 0;
        }
        bool exchanged = false;
        if (rand() % 2 == 0)
        {
            int index = rand() % (res.size() - 1);
            int op1 = res[index].first;
            int op2 = res[index + 1].first;
            bool is_pre = false;
            for (int j = heads[op1]; j != -1; j = nex[j])
            {
                if (to[j] == op2)
                {
                    is_pre = true;
                    break;
                }
            }
            if (!is_pre)
            {
                swap(res[index], res[index + 1]);
                exchanged = true;
            }
        }
        if (!exchanged)
        {
            int index = rand() % (res.size() - 1);
            int op1 = res[index].first;
            int op2 = res[index + 1].first;
            swap(res[index], res[index + 1]);
        }
        for (int i = 0; i < n; i++)
        {
            q_free_t[i] = 0;
        }
        for (int i = 0; i < res.size(); i++)
        {
            int op = res[i].first;
            int card = res[i].second;
            long long start_t = q_free_t[card];
            vector<int> v;
            for (int i = rheads[op]; i != -1; i = rnex[i])
            {
                int pre_op = rto[i];
                v.emplace_back(pre_op);
            }
            sort(v.begin(), v.end(), [&](int i, int j) {
                return last_trans_end_t[i] < last_trans_end_t[j];
            });
            for (auto pre_op : v) {
                if (last_trans_end_t[pre_op] > start_t) {   
                    start_t = last_trans_end_t[pre_op];
                }
                int result_card = op_result_card[pre_op];
                start_t += ((result_card == card) ? 0 : trans_cost[pre_op]);
            }
            op_result_card[op] = card;
            last_trans_end_t[op] = start_t + cal_cost[op];
            cost = max(cost, last_trans_end_t[op]);
            q_free_t[card] = last_trans_end_t[op];
            for( int i = rheads[op]; i != -1; i = rnex[i])
            {
                int pre_op = rto[i];
                last_trans_end_t[pre_op] = start_t;
                op_result_card[pre_op] = card;
            }
        }
        if (cost < best_cost)
        {
            best_cost = cost;
            best_res = res;
            cout << "find best cost in optimize:" << best_cost << endl;
        }
    }
    // 判题器
    long long judge() {
        long long cost = 0;
        vector<long long> op_trans_time(m, 0);
        vector<int> op_current_card(m, -1);
        vector<int> in_degree_judge(m, 0);
        vector<long long> card_time(n, 0);
        for (int i = 0; i < m; i++) {
            for (int j = heads[i]; j != -1; j = nex[j]) {
                in_degree_judge[to[j]]++;
            }
        }
        for (auto &p : best_res) {
            int op = p.first;
            int card = p.second;
            if (in_degree_judge[op] != 0) {
                return -1;
            }
            long long start_t = card_time[card];
             vector<int> v;
            for (int i = rheads[op]; i != -1; i = rnex[i])
            {
                int pre_op = rto[i];
                v.emplace_back(pre_op);
            }
            sort(v.begin(), v.end(), [&](int i, int j) {
                return op_trans_time[i] < op_trans_time[j];
            });
            for (auto pre_op : v) {
                if (op_trans_time[pre_op] > start_t) {
                    start_t = op_trans_time[pre_op];
                }
                int result_card = op_current_card[pre_op];
                start_t += ((result_card == card) ? 0 : trans_cost[pre_op]);
            }
            op_trans_time[op] = start_t + cal_cost[op];
            op_current_card[op] = card;
            card_time[card] = op_trans_time[op];
            for (int i = rheads[op]; i != -1; i = rnex[i]) {
                int pre_op = rto[i];
                op_current_card[pre_op] = card;
                op_trans_time[pre_op] = start_t;
            }
            cost = max(cost, op_trans_time[op]);

            for (int i = heads[op]; i != -1; i = nex[i]) {
                int nex_op = to[i];
                in_degree_judge[nex_op]--;
            }
        }
        return cost;
    }
};

const int thread_size = 12; // 并行线程数
const int run_upper_time = 60; // 程序执行时间

std::vector<std::pair<int, int>> solve(int n, int m, const std::vector<std::vector<int>> &graph)
{
    auto start = chrono::high_resolution_clock::now();
    vector<Solution> solutions;
    if (n == 1 or m == 1)
    {
        solutions.push_back(Solution(n, m, graph, cal_use_times, trans_use_times));
        solutions[0].work();
        solutions[0].write_res_to_file(output_path);
        solutions[0].show_best_res(ids);
        return solutions[0].get_best_res().second;
    }
    for (int i = 0; i < thread_size; i++)
    {
        solutions.push_back(Solution(n, m, graph, cal_use_times, trans_use_times));
    }
    vector<pthread_t> threads(thread_size);
    
    int initial_res_time = run_upper_time / 5 * 4;
    int optimize_time = run_upper_time - initial_res_time;
    while (1)
    {
        for (int i = 0; i < threads.size(); i++)
        {
            int ret = pthread_create(&threads[i], NULL, [](void *arg) -> void *
                                     {
                    Solution* sol = static_cast<Solution*>(arg);
                    sol->work();
                    return nullptr; }, &solutions[i]);
        }
        for (int i = 0; i < threads.size(); i++)
        {
            pthread_join(threads[i], NULL);
        }
        // for(int i=0;i<solutions.size();i++)
        // {
        //     solutions[i].write_res_to_file(output_path);
        // }
        auto end = chrono::high_resolution_clock::now();
        chrono::duration<double> elapsed = end - start;
        if (elapsed.count() >= run_upper_time) // 运行时间达到上限的一半，停止
            break;
    }
    for (int i = 1; i < solutions.size(); i++)
    {
        Solution::merge_best_res(solutions[0], solutions[i]);
    }
    for (int i = 1; i < solutions.size(); i++)
    {
        solutions[i].cp_best_res(solutions[0]);
    }
    // 优化阶段
    start = chrono::high_resolution_clock::now();
    while (1)
    {
        for (int i = 0; i < threads.size(); i++)
        {
            int ret = pthread_create(&threads[i], NULL, [](void *arg) -> void *
                                     {
                    Solution* sol = static_cast<Solution*>(arg);
                    sol->optimize_best_res();
                    return nullptr; }, &solutions[i]);
        }
        for (int i = 0; i < threads.size(); i++)
        {
            pthread_join(threads[i], NULL);
        }
        auto end = chrono::high_resolution_clock::now();
        chrono::duration<double> elapsed = end - start;
        if (elapsed.count() >= run_upper_time) // 运行时间达到上限的一半，停止
            break;
    }
    for (int i = 1; i < solutions.size(); i++)
    {
        Solution::merge_best_res(solutions[0], solutions[i]);
    }
    cout<<"initial best cost: " << solutions[0].get_best_res().first << endl;
    cout << "judge result: " << solutions[0].judge() << endl;
    // solutions[0].show_best_res(ids);
    return solutions[0].get_best_res().second;
}

// 主程序接口
std::vector<std::pair<int, int>> ExecuteOrder(const std::vector<Node *> &all_nodes, int card_num)
{
    int n = card_num;
    int m = all_nodes.size();
    std::vector<std::vector<int>> graph(m);
    for (auto &node : all_nodes) {
        for (auto &pre : node->inputs()) {
            graph[node->id()].emplace_back(pre->id());
        }
    }
    return solve(n, m, graph);
}

int main()
{
    // 删除旧的output文件
    remove(output_path.c_str());
    init(input_path[0]);
    auto start = chrono::high_resolution_clock::now();
    ExecuteOrder(nodes, n);
    auto end = chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "执行耗时: " << duration.count() << " 毫秒" << std::endl;
    return 0;
}